;;; Find the largest prime factor of a composite number.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
(defun prime-factors (n)
  (defun pf-inner (k result)
	(if (= k 1)
	    result
		((lambda (y)
		   (pf-inner (/ k y) (append result (list y)))) (first-prime-factor k))))
  (defun last-factor (x)
	(>= (expt x 2) n))
  (pf-inner n '()))

(defun first-prime-factor (x)
	(do ((i 2 (1+ i)))
	  ((zerop (mod x i)) i)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; @see p12.lisp
(defun primfac (num)
  (when (> num 1)
    (do ((x 2 (1+ x)))
        ((zerop (mod num x)) (cons x (primfac (/ num x))))
		)))
;;; TODO 
;(defun primfac-improve (num)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
(defun p3 (&optional (input-num 600851475143))
	(format t "~a~%" (time (prime-factors input-num)))
	(format t "~a~%" (time (primfac input-num))))

(p3)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
"
Sad old Unix hacker:
$ factor 317584931803
317584931803: 67 829 1459 3919 
"
;;;
